import sys

__all__ = ['Heap', 'PriorityQueue']

class NodeHeap(object):
    """An ordered set optimized for finding the greatest value element.
    
    This is a binary max heap."""

    class heapNode(object):

        def __init__(self, value):
            self.parent = None
            self.left = None
            self.right = None
            self.value = value

    def __init__(self):
        self.root = None
        self.last = None

    def find_max(self):
        return self.root.value

    def pop_max(self):
        toReturn = self.root

        newRoot = self.last
        self._delete_last()

        newRoot.left = self.root.left
        newRoot.right = self.root.right
        newRoot.parent = None
        
        if self.root.left is not None:
            self.root.left.parent = newRoot
        if self.root.right is not None:
            self.root.right.parent = newRoot

        self.root = newRoot
        self._bubble_down(self.root)

        return toReturn.value
          

    def insert(self, value):
        node = NodeHeap.heapNode(value)
        if self.root is None:
            self.root = node
            self.last = node
            return

        parent = self._find_next_open()
        
        node.parent = parent
        if parent.left is None:
            parent.left = node
        else:
            parent.right = node
        
        self.last = node
        self._bubble_up(node)

    def _bubble_up(self, node):
        while node.parent is not None and node.parent.value < node.value:
            if node == self.last:
                self.last = node.parent
            if node.parent == self.root:
                self.root = node

            parent = node.parent
            grandparent = parent.parent
            parent.parent = node
            node.parent = grandparent

            if node.left is not None:
                node.left.parent = parent
            if node.right is not None:
                node.right.parent = parent

            if parent.right == node:
                parentLeft = parent.left
                parent.left = node.left
                parent.right = node.right
                node.left = parentLeft
                node.right = parent
                if parentLeft is not None:
                    parentLeft.parent = node
            else:
                parentRight = parent.right
                parent.left = node.left
                parent.right = node.right
                node.left = parent
                node.right = parentRight
                if parentRight is not None:
                    parentRight.parent = node

            if grandparent is not None:
                if grandparent.right == parent:
                    grandparent.right = node
                else:
                    grandparent.left = node


    def _bubble_down(self, node):
        swapNode = None
        while node.left is not None or node.right is not None:
            if node.left is None or (node.right is not None and node.right.value > node.left.value):
                swapNode = node.right
            else:
                swapNode = node.left

            if node.value > swapNode.value:
                break
            else:
                self._bubble_up(swapNode)

    def _find_next_open(self):
        node = self.last
        while node.parent is not None and node.parent.right == node:
            node = node.parent

        if node.parent is None:
            # tree is full. add to the bottom left
            while node.left is not None:
                node = node.left
        else:
            # since the tree is always filled from left to right, if we started
            # at the rightmost node on the bottom level and we've found that we
            # were on the left side of a subtree, there must be space on the bottom
            # level of the corresponding right subtree
            node = node.parent
            if node.right is not None:
                node = node.right
                while node.left is not None:
                    node = node.left

        return node

    def _delete_last(self):
        node = self.last
        while node.parent is not None and node.parent.left == node:
            node = node.parent

        if node.parent is None:
            # last was the first node on its level. new last is the node
            # on the far right
            while node.right is not None:
                node = node.right
        else:
            node = node.parent.left
            while node.right is not None:
                node = node.right

        # remove from the tree
        if self.last.parent is not None:
            if self.last.parent.left == self.last:
                self.last.parent.left = None
            else:
                self.last.parent.right = None

        # save new last node
        self.last = node


class Heap:
    """An ordered set optimized for finding the greatest value element.
    
    This is a binary max heap."""
    def __init__(self):
        self._arr = []

    def find_max(self):
        if len(self._arr) > 0:
            return self._arr[0]
        else:
            return None

    def pop(self):
        if len(self._arr) == 0:
            return None

        toReturn = self._arr[0]
        self._arr[0] = self._arr[-1]
        del self._arr[-1]
        if len(self._arr) > 0:
            self._bubble_down(0)
        return toReturn

    def insert(self, value):
        self._arr.append(value)
        self._bubble_up(len(self._arr) - 1)

    def _bubble_down(self, index):
        val = self._arr[index]
        iLeft, left = self._get_left(index)
        iRight, right = self._get_right(index)

        while ((left is not None and val < left) or (right is not None and val < right)):
            if right is None or left > right:
                self._arr[iLeft], self._arr[index] = self._arr[index], self._arr[iLeft]
                index = iLeft
            elif left is None or right >= left:
                self._arr[iRight], self._arr[index] = self._arr[index], self._arr[iRight]
                index = iRight

            iLeft, left = self._get_left(index)
            iRight, right = self._get_right(index)

        return index


    def _bubble_up(self, index):
        val = self._arr[index]
        iParent, parent = self._get_parent(index)
        
        while (parent is not None and val > parent):
            self._arr[index], self._arr[iParent] = self._arr[iParent], self._arr[index]
            index = iParent
            iParent, parent = self._get_parent(index)

        return index

    def _get_parent_index(self, childIndex):
        return ((childIndex + 1) // 2) - 1 

    def _get_left_index(self, parentIndex):
        return parentIndex * 2 + 1

    def _get_right_index(self, parentIndex):
        return parentIndex * 2 + 2

    def _get_parent(self, index):
        if index == 0:
            return (None, None)

        iParent = self._get_parent_index(index)
        return iParent, self._arr[iParent]

    def _get_left(self, parentIndex):
        iLeft = self._get_left_index(parentIndex)
        if iLeft < len(self._arr):
            return iLeft, self._arr[iLeft]
        else:
            return (None, None)

    def _get_right(self, parentIndex):
        iRight = self._get_right_index(parentIndex)
        if iRight < len(self._arr):
            return iRight, self._arr[iRight]
        else:
            return (None, None)

    def __len__(self):
        return len(self._arr)


class PriorityQueue:
    """A max priority queue"""

    def __init__(self):
        self._heap = Heap()

    def pop(self):
        priority, key = self._heap.pop()
        return (key, priority)

    def peek(self):
        priority, key = self._heap.find_max()
        return (key, priority)

    def insert(self, key, priority):
        self._heap.insert((priority, key))

    def __len__(self):
        return len(self._heap)


class PriorityQueueInverter:
    """A wrapper that inverts the priority ordering of the inner PriorityQueue"""

    def __init__(self, innerQueue):
        self._innerQueue = innerQueue

    def pop(self):
        """Remove and return the item at the front of the queue"""
        key, priority = self._innerQueue.pop()
        return (key, -priority) 

    def peek(self):
        return self._innerQueue.peek()

    def insert(self, key, priority):
        """Insert the key item with the given priority."""
        self._innerQueue.insert(key, -priority)

    def __len__(self):
        return len(self._innerQueue)

if __name__ == '__main__':
    myHeap = Heap()
    myHeap.insert(12)
    myHeap.insert(8)
    myHeap.insert(2)
    myHeap.insert(14)
    myHeap.insert(20)
    myHeap.insert(7)

    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())

    myHeap.insert(100)
    myHeap.insert(1)
    myHeap.insert(99)
    myHeap.insert(2)
    myHeap.insert(98)
    myHeap.insert(3)

    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
    print(myHeap.pop())
